GATE CSE 2010
Q21.
Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?Q22.
Newton-Raphson method is used to compute a root of the equation x^{2} -13=0 with 3.5 as the initial value. The approximation after one iteration isQ23.
A 5-stage pipelined processor has Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Write Operand (WO) stages. The IF, ID, OF and WO stages take 1 clock cycle each for any instruction. The PO stage takes 1 clock cycle for ADD and SUB instructions, 3 clock cycles for MUL instruction, and 6 clock cycles for DIV instruction respectively. Operand forwarding is used in the pipeline. What is the number of clock cycles needed to execute the following sequence of instructions?Q24.
Consider a company that assembles computers. The probability of a faulty assembly of any computer is p. The company therefore subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of q. What is the probability of a computer being declared faulty?Q27.
Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned. Which one of the following statements describes the properties achieved?Q28.
The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0=1, S1=0, S2=0. How many times will process P0 print '0'? How many times will process P0 print '0'?Q29.
Suppose the predicate F(x,y,t) is used to represent the statement that person x can fool person y at time t. which one of the statements below expresses best the meaning of the formula \forall x \exists y \exists t(\neg F (x, y, t))?Q30.
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?